package practise.tree;

import org.springframework.test.annotation.NotTransactional;

import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.Queue;
import java.util.Stack;

/**
 * Create a bin tree, include CRUD, and calculate the width and height of the tree
 * Sum the nodes in one level
 */
public class BinTree {
    private Node root;

    /**
     * create a sort tree
     * @param amount
     * @return
     */
    public Node createSortTree(int amount){
        Node root = new Node();
        for(int i =0 ; i < amount ; i ++){
            insertNodeUnder(root, i);
        }

        return root;
    }

    /**
     * insert the node under sort
     * @param node
     * @param value
     * @return
     */
    public Node insertNodeUnder(Node node, int value){
        if(node == null){
            node = new Node();
            node.setValue(value);
            return node;
        }

        if(value <node.getValue()){
           return insertNodeUnder(node.getLeftNode(),value);
        }
        else{
            return insertNodeUnder(node.getRightNode(),value);
        }

    }

    /**
     * create a unsorted tree
     * @param size
     * @return
     */
    public Node createTree(int size){
        return createTree(null, 1, size);

    }
    private Node createTree(Node node, int index , int size){
        if(node==null){
            node =  new Node();
            node.setValue(index);
        }
        if(index*2<=size){
            node.setLeftNode(createTree(node.getLeftNode(), index * 2, size));
        }
        if(index*2+1 <=size){
            node.setRightNode(createTree(node.getRightNode(), index * 2 + 1, size));
        }
        return node;
    }

    /**
     * sum the value in a level, calculate from the root
     * @param root
     * @param level
     * @return
     */
    public int sumLevel(Node root, int level){
        return sumLevel(root, 1,level);
    }

    /**
     * sum the value in a level, calculate from the node
     * @param cur
     * @param level
     * @return
     */
    public int sumLevel(Node node, int cur, int level){
        if(level!=cur){
            return sumLevel(node.getLeftNode(),cur+1,level)+ sumLevel(node.getRightNode(),cur+1,level);
        }
        else{
            System.out.println("level:" + level + "value:" +node.getValue());
            return node.getValue();
        }
    }

    /**
     * calculate the height
     * @param root
     * @return
     */
    public int height(Node root){
        if(root==null){
            return 0;
        }
        else{
            int sumLeft = height(root.getLeftNode());
            int sumRight = height(root.getRightNode());
            if(sumLeft>sumRight){
                return sumLeft+1;
            }
            else {
                return sumRight+1;
            }
        }
    }

    /**
     * calculate the width
     * @param node
     * @return
     */
    public int weith(Node node){

        if(node.getLeftNode()==null && node.getRightNode()==null){
            return 1;
        }
        else{
            int sumLeft = weith(node.getLeftNode());
            int sumRight = weith(node.getRightNode());
            return sumLeft+sumRight;
        }
    }

    public void preOrder(Node root){
        if(root!=null){
        System.out.println(root.getValue());
        
        preOrder(root.getLeftNode());
        preOrder(root.getRightNode());
        }

    }

    public void midOrder(Node node){

        preOrder(root.getLeftNode());
        System.out.println(root.getValue());
        preOrder(root.getRightNode());
    }

    public void afterOrder(Node node){
        preOrder(root.getLeftNode());

        preOrder(root.getRightNode());
        System.out.println(root.getValue());
    }

    public Stack depthOrder(Node node){
        Stack<Node> nodeStack = new Stack<Node>();
        depthOrder(node,nodeStack);
        return nodeStack;
    }

    private void depthOrder(Node node, Stack stack){
        if(node ==null){
            return;
        }
        else{
            depthOrder(node.getRightNode(),stack);
            depthOrder(node.getLeftNode(),stack);
            stack.add(node);
        }
    }

    /**
     * cannot use the recur method for the width order
     * @param node
     * @return
     */
    public Queue<Node> widthOrder(Node node){
        Queue<Node> nodeQueue = new ArrayDeque<Node>();
        widthOrder(node, nodeQueue);
        return nodeQueue;
    }

    public void widthOrder(Node node, Queue<Node> nodeQueue){
        if(node==null){
            return;
        }
        else{
            nodeQueue.offer(node);
            widthOrder(node.getLeftNode(),nodeQueue);

            widthOrder(node.getRightNode(),nodeQueue);

        }
    }


    public static void main(String[] args){
        BinTree binTree = new BinTree();
        Node node = binTree.createTree(15);
        System.out.println(binTree.sumLevel(node,3));
        binTree.preOrder(node);
        System.out.println("height:" + binTree.height(node));
        System.out.println("weigth:" + binTree.weith(node));
        Stack<Node> stack = binTree.depthOrder(node);
        System.out.println("Stack:" );

        while(!stack.isEmpty()){
            System.out.println(stack.pop().getValue());
        }
        System.out.println("Stack2:" );
        IteratableDepth depthIterator = new IteratableDepth(node);
        for(Node node1 : depthIterator){
            System.out.println(node1.getValue());
        }

        Queue<Node> queue = binTree.widthOrder(node);
        System.out.println("Queue:" );//failed

        while(!queue.isEmpty()){
            System.out.println(queue.poll().getValue());
        }

        System.out.println("Queue2:" );
        IterableWidth iterableWidth = new IterableWidth(node);
        for(Node node1 : iterableWidth){
            System.out.println(node1.getValue());
        }
    }
}

class IterableWidth implements Iterable<Node>{

    private Node node ;
    public IterableWidth(Node node){
       this.node = node;
    }
    @Override
    public Iterator<Node> iterator() {
        return new WidthIterator(node);
    }
}

class WidthIterator implements  Iterator<Node>{

    public Queue<Node> queue;
    public WidthIterator(Node node){
      queue = new ArrayDeque<Node>();
        queue.offer(node);
    }


    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }

    @Override
    public Node next() {
        Node node = queue.poll();
        if(node.getLeftNode()!=null)
            queue.offer(node.getLeftNode());
        if(node.getRightNode()!=null)
            queue.offer(node.getRightNode());
        return node;
    }

    @Override
    public void remove() {

    }
}

class IteratableDepth implements Iterable<Node>{
    private Node node ;
    public IteratableDepth(Node node){
        this.node = node;
    }

    @Override
    public Iterator<Node> iterator() {
        return new DepthIterator(node);
    }
}

class DepthIterator implements Iterator<Node>{

    private Stack<Node> nodeStack = new Stack<Node>();
    public DepthIterator(Node node){
        nodeStack.push(node);
    }

    @Override
    public boolean hasNext() {
        return !nodeStack.isEmpty();
    }

    @Override
    public Node next() {
        Node node = nodeStack.pop();
        if(node.getRightNode()!=null)
            nodeStack.push(node.getRightNode());
        if(node.getLeftNode()!=null)
            nodeStack.push(node.getLeftNode());

        return node;
    }

    @Override
    public void remove() {

    }
}

class Node{
    public Node(){}
    private int value;
    private Node leftNode;
    private Node rightNode;

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

}
